import java.util.List;

/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/5/12
 * \* Time: 1:49
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 反转链表II {
    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    public ListNode reverseBetween(ListNode head, int left, int right) {
        //虚拟头结点
        ListNode res=new ListNode(0);
        res.next=head;
        ListNode pre=res;
        //让node指向起始节点的前一个节点
        for(int i=1;i<left;i++){
            pre=pre.next;
        }

        //cur指向要反转的第一个节点
        ListNode cur=pre.next;
        ListNode next;
        //头插法反转链表
        for(int i = 0; i < right - left; i++){
            next=cur.next;
            cur.next=next.next;
            next.next=pre.next;
            pre.next=next;
        }
        return res.next;
    }
}